This paper shows that Mixed Packing Covering Linear programs can be eps-approximated in O(1/eps) iterations. This work builds on Sherman's approach to max flow. This is a strong result on an important class of problems. Optimization problems of this nature arise frequently in machine learning applications and reducing the eps dependence from quadratic to linear is a significant improvement. The reviewers liked the result and the presentation and strongly supported acceptance.

In this paper, we give a faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a 1 \eps approximate solution in time O(Nw/ \varepsilon), where N is number of nonzero entries in the constraint matrix, and w is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires O(N\sqrt{n}w/ \eps) time, where n is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS'17] to obtain the best dependence on \varepsilon while breaking the infamous \ell_{\infty} barrier to eliminate the factor of \sqrt{n} .

In this paper, we give a faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a $1 \eps$ approximate solution in time $O(Nw/ \varepsilon)$, where $N$ is number of nonzero entries in the constraint matrix, and $w$ is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires $O(N\sqrt{n}w/ \eps)$ time, where $n$ is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS'17] to obtain the best dependence on $\varepsilon$ while breaking the infamous $\ell_{\infty}$ barrier to eliminate the factor of $\sqrt{n}$.